package com.aqie.medium.sort;

/**
 * 912 排序数组 todo
 */
public class SortArray {
    /**
     * 1, 快速排序 12ms
     * @param nums
     * @return
     */
    public int[] sortArray(int[] nums) {
        int n=nums.length;
        quickSort(nums,0,n-1);
        return nums;
    }
    private void quickSort(int[] nums, int l, int r){
        if(l>=r)    return;
        int p=partition(nums,l,r);
        quickSort(nums,l,p-1);
        quickSort(nums,p+1,r);
    }
    private int partition(int[] nums, int l, int r){
        int value=nums[l];
        int j=l;
        for(int i=l+1;i<=r;i++){
            if(nums[i]<value){
                swap(nums,i,j+1);
                j++;
            }
        }
        swap(nums,l,j);
        return j;
    }
    private void swap(int[] nums, int i, int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }

    /**
     * 2, 归并排序  20ms
     * @param nums
     * @return
     */
    public int[] sortArray2(int[] nums) {
        int n=nums.length;
        mergeSort(nums,0,n-1);
        return nums;
    }
    private void mergeSort(int[] nums, int l, int r){
        if(l>=r)    return;
        int mid=(l+r)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        merge(nums,l,mid,r);
    }
    private void merge(int[] nums, int l, int mid, int r){
        int[] aux=new int[r-l+1];
        if (r + 1 - l >= 0) System.arraycopy(nums, l, aux, 0, r + 1 - l);
        int i=l,j=mid+1;
        for(int k=l;k<=r;k++){
            if(i>mid){
                nums[k]=aux[j-l];
                j++;
            }
            else if(j>r){
                nums[k]=aux[i-l];
                i++;
            }
            else if(aux[i-l]>aux[j-l]){
                nums[k]=aux[j-l];
                j++;
            }else{
                nums[k]=aux[i-l];
                i++;
            }
        }
    }

    /**
     * 3, 桶排序 12ms
     * @param nums
     * @return
     */
    public int[] sortArray3(int[] nums) {
        int[] bucket=new int[100000];
        for(int num:nums){
            bucket[num+50000]++;
        }
        int index=0;
        for(int i=0;i<bucket.length;i++){
            int num=bucket[i];
            while(num!=0){
                nums[index++]=i-50000;
                num--;
            }
        }
        return nums;
    }
}
